/*
 * File:   inernode.h
 * Author: Stripped
 *
 * Created on April 18, 2009, 10:02 AM
 */

#ifndef _INERNODE_H
#define _INERNODE_H

#include "Node.h"
#include "KeyValueEntity.h"
#include <stdexcept>
#include "TreeUtils.h"
#include "LeafNode.h"
#include <algorithm>

using namespace std;

template <class TKey, class TValue>
class KeyValuePair;

template <class TKey, class TValue>
class Node;

template <class TKey, class TValue>
class InerNode : public Node <TKey, TValue>
{
    //typedef KeyValuePair<TKey, TValue> KeyValuePair;
    typedef Node<TKey, TValue> INode;

public:
    /**
     * Constructor: Creates an InerNode
     *
     * @param  nodeMaxSize: is the max size of the node, default value = 2
     * @param  parent: node that will be parent of the new node, default value = NULL
     */
    InerNode(unsigned int nodeMaxSize = 2, Node<TKey, TValue>* parent = NULL) : Node<TKey, TValue>(nodeMaxSize, parent)
    {
        this->children.reserve(nodeMaxSize + 2);
    }

    /**
     * Destructor
     *
     */
    virtual ~InerNode()
    {
        for (unsigned int i = 0 ; i < children.size() ; i++)
        {
            if (children[i] != NULL)
            {
                delete children.at(i);
            }
        }
    }

    /**
     * Adds a key-value pair into the tree.
     *
     * Throws an std::logic_exception if the key exists in the tree.
     *
     * @param  TKey key which identifies the key-value pair
     * @param  TValue value of the key-value pair
     */
    virtual INode* put(const TKey& key, const TValue& value)
    {
        unsigned int begin = 0;
        unsigned int end = this->elements.size();
        unsigned int middle = 0;

        if (this->elements.size() == 0)
        {
            this->elements.insert(this->elements.begin(),  KeyValuePair<TKey, TValue> (key, value));
            return NULL;
        }

        // Modified Binary Search which goes down within the tree.
        while (begin < end)
        {
            middle = begin + ((end - begin) / 2);

            if (key < this->elements[middle].key)
            {
                if ((middle == 0) || (key > this->elements[middle - 1].key))
                {
                    return this->children[middle]->put(key, value);
                }
                else
                {
                    end = middle;
                }
            }
            else if (key == this->elements[middle].key)
            {
                throw ios_base::failure("No se puede agregar una clave duplicada.");
            }
            else if (key > this->elements[middle].key)
            {
                if ((middle == this->elements.size() - 1) || (key < this->elements[middle + 1].key))
                {
                	return this->children[middle + 1]->put(key, value);
                }
                else
                {
                    begin = middle + 1;
                }
            }
        }

        return NULL;
    }

    /**
     * Returns the value of a specified key
     *
     * Throws std::logic_error if the key does not exists
     *
     * @param  TKey key which value you wish to retrieve
     * @return TValue value which matches the given key
     */
    virtual TValue& get(const TKey& key)
    {
        unsigned int begin = 0;
        unsigned int end = this->elements.size();
        unsigned int middle = 0;

        if (this->elements.size() == 0)
        	throw ios_base::failure("Clave no encontrada.");

        // Modified Binary Search which goes down within the tree.
        while (begin < end)
        {
            middle = begin + ((end - begin) / 2);

            if (key < this->elements[middle].key)
            {
                if ((middle == 0) || (key > this->elements[middle - 1].key))
                {
                    return this->children[middle]->get(key);
                }
                else
                {
                    end = middle;
                }
            }
            else if (key == this->elements[middle].key)
            {
                return this->elements[middle].value;
            }
            else if (key > this->elements[middle].key)
            {
                if ((middle == this->elements.size() - 1) || (key < this->elements[middle + 1].key))
                {
                    return this->children[middle + 1]->get(key);
                }
                else
                {
                    begin = middle + 1;
                }
            }
        }

        throw ios_base::failure("Clave no encontrada.");
    }

    /**
     * Removes an element from the node.
     * NOTE: Since remove is only intended as part of an update, it does not fixes underflow after deletion.
     *
     * Throws std::logic_error if the key is not present
     *
     * @param key to remove
     */
    virtual void remove (const TKey& key)
    {
        unsigned int begin = 0;
        unsigned int end = this->elements.size();
        unsigned int middle = 0;
         KeyValuePair<TKey, TValue>  aux(0);
        typename std::vector< KeyValuePair<TKey, TValue> >::iterator it;

        // The node is empty, it has no children and no keys
        if (this->elements.size() == 0)
        	throw ios_base::failure("Clave no encontrada. No es posible borrar el registro.");

        // Modified Binary Search which goes down within the tree.
        while (begin < end)
        {
            middle = begin + ((end - begin) / 2);

            if (key < this->elements[middle].key)
            {
                if ((middle == 0) || (key > this->elements[middle - 1].key))
                {
                    //return this->children[middle]->remove(key);
                	this->children[middle]->remove(key);
                	return;
                }
                else
                {
                    end = middle;
                }
            }
            else if (key == this->elements[middle].key)
            {
                aux = this->children[middle + 1]->swap(*it);

                it = TreeUtils::binary_search(this->elements.begin(), this->elements.end(),  KeyValuePair<TKey, TValue> (key));

                *it = aux;

                this->children[middle + 1]->remove(key);
                return;
            }
            else if (key > this->elements[middle].key)
            {
                if ((middle == this->elements.size() - 1) || (key < this->elements[middle + 1].key))
                {
                    //return this->children[middle + 1]->remove(key);
                	this->children[middle + 1]->remove(key);
                	return;
                }
                else
                {
                    begin = middle + 1;
                }
            }
        }
    }

    /**
     * Searchs for a specified key and returns true if exists
     *
     * @param  TKey key which value you wish to find
     * @return bool True if the key exists, False if it doesn't
     */
    virtual bool has(const TKey& key) const
    {
        unsigned int begin = 0;
        unsigned int end = this->elements.size();
        unsigned int middle = 0;

        // The node is empty, so it doesn't has the key
        if (this->elements.size() == 0)
            return false;

        // Modified Binary Search which goes down within the tree.
        while (begin < end)
        {
            middle = begin + ((end - begin) / 2);

            if (key < this->elements[middle].key)
            {
                if ((middle == 0) || (key > this->elements[middle - 1].key))
                {
                    return this->children[middle]->has(key);
                }
                else
                {
                    end = middle;
                }
            }
            else if (key == this->elements[middle].key)
            {
                return true;
            }
            else if (key > this->elements[middle].key)
            {
                if ((middle == this->elements.size() - 1) || (key < this->elements[middle + 1].key))
                {
                    return this->children[middle + 1]->has(key);
                }
                else
                {
                    begin = middle + 1;
                }
            }
        }

        return false;
    }

    /**
     * counts the amount of elements in the node.
     *
     * @return returns the elements count
     */
    virtual unsigned int elementsCount() const
    {
        int nodes = 0;

        // for each children, count the elements
        for (unsigned int i = 0; i < this->children.size(); i++)
        {
            if (children[i] != NULL)
            {
                nodes += children[i]->elementsCount();
            }
        }

        // add our own element
        nodes += this->elements.size();

        return nodes;
    }

    /**
     * Swaps the element for the smaller in the node.
     *
     * @param element: KeyValuePair to swap
     * @return returns the old KeyValuePair that was replaced
     */
    virtual  KeyValuePair<TKey, TValue>  swap( KeyValuePair<TKey, TValue>  element)
    {
        // nothing occurs, the swap is done in a leaf node.
        return this->children.front()->swap(element);
    }

    /**
     * Adds the children into the correct position.
     *
     * @param Node<TKey, TValue>* the node children to insert.
     * @param unsigned int at the position in which to insert the node.
     */
    virtual void forceAddChildren(INode* node, unsigned int at)
    {
        typename std::vector<INode*>::iterator it = this->children.begin();

        // Move the iterator to the correct position
        for (unsigned int i = 0; i < at; i++)
            it++;

        // Insert the children in the position
        node->setParent(this);
        this->children.insert(it, node);
    }

    /**
     * Adds the children into the correct position.
     *
     * @param Node<TKey, TValue>* the node children to insert.
     */
    virtual void forcePushBackChildren(Node<TKey, TValue>* node)
    {
        node->setParent(this);
        this->children.push_back(node);
    }

    /**
     * Removes the first element of the list
     *
     */
    virtual void forceRemoveFirstElement()
    {
        this->elements.erase(this->elements.begin());

        // Don't free this memory, since it's a reference that it's still being used.
        this->children.erase(this->children.begin());
    }

    /**
     * For debuggin purposes, it prints the tree
     *
     */
    /*
    virtual void printNode()
    {
        unsigned int pos = 0;

        std::cout << "< ";
        while (pos < this->elements.size())
        {
            //std::cout << "<" << this->elements[pos].key << "," << this->elements[pos].value << ")" << " ";
            std::cout << this->elements[pos].key << " ";
            pos++;
        }
        std::cout << ">";

        std::cout << std::endl;

        pos = 0;

        while (pos < this->children.size())
        {
            this->children[pos]->printNode();
            pos++;
            if (pos != this->children.size())
                std::cout << "\t" << "||" << "\t";
        }
        std::cout << std::endl;
    }
*/
    /**
     * Fills the vector sent as parameter with all the elements of the tree (recursive)
     *
     * @param vector to fill
     */
    virtual void getAllElements(std::vector< KeyValuePair<TKey, TValue> > &vector)
    {
        for (unsigned int i = 0; i < this->elements.size(); i++)
        {
            vector.push_back( this->elements[i]);
            this->children[i]->getAllElements(vector);
        }

        this->children.back()->getAllElements(vector);
    }

protected:
    std::vector<INode*> children;

    /**
     * Splits the node in half.
     *
     * Creates a new sibling node with all the elements bigger (to the right) of the key on the "split position" (nodeMaxSize /2).
     *
     * @return returns the new  Node<TKey, TValue> sibling
     */
    INode* split()
    {
        // if I'm an iner node, my siblings are InerNodes
        INode* sibling = new InerNode<TKey, TValue>(this->nodeMaxSize, this->parentNode);
        unsigned int splitPosition = this->nodeMaxSize / 2;
        //unsigned int at = 0;

        // Move all the elements (including the key to promote) to the new sibling ( old -> new )
        for (unsigned int i = splitPosition+1; i < (unsigned int)(this->nodeMaxSize + 1) ; i++)
        {
            // Add the element and get the position in which it was inserted
            //at = sibling->forceAddElement(this->elements.at(i));
            sibling->forcePushBackElement(this->elements.at(i));

            // Insert the children in the corresponding nodeMaxSize
            //sibling->forceAddChildren(this->children.at(i), at);
            sibling->forcePushBackChildren(this->children.at(i));
        }

        // Add the last children of the original node
        //sibling->forceAddChildren(this->children.at(this->nodeMaxSize + 1), at + 1);
        sibling->forcePushBackChildren(this->children.at(this->nodeMaxSize + 1));

        // Erase all the copied children references from the original node.
        this->children.erase(this->children.begin() + splitPosition + 1, this->children.end());

        // Erase all the copied elements from the original node
        this->elements.erase(this->elements.begin() + splitPosition, this->elements.end());

        return sibling;
    }

private:
    InerNode(const InerNode<TKey, TValue>&);
    InerNode<TKey, TValue>& operator=(const InerNode<TKey, TValue>&);

};

#endif  /* _INERNODE_H */
